import java.math.BigInteger;
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

// 可以阅读一下博客
// https://blog.csdn.net/qq_51641311/article/details/127839121
public class Classic_CRT_Threshold_Secret_Sharing {

    private final Random RND = new Random();
    private static final Scanner scanner = new Scanner(System.in);

    // 安全参数，按比特位算
    private final int parameter;
    // 总共的秘密子份额数量
    private final int sharingNums;
    // 能够正常恢复秘密的门限值
    private final int threshold;
    // 所要共享的秘密
    private final BigInteger secret;
    // 秘密子份额数组
    private final BigInteger[] subSecrets;

    public Classic_CRT_Threshold_Secret_Sharing(int parameter, int sharingNums, int threshold) {
        this.parameter = parameter;
        this.sharingNums = sharingNums;
        this.threshold = threshold;
        this.secret = new BigInteger(parameter, RND);
        this.subSecrets = new BigInteger[sharingNums];
    }

    public static Classic_CRT_Threshold_Secret_Sharing getInstance() {
        System.out.print("请输入安全参数大小:");
        int parameter = scanner.nextInt();
        System.out.print("请输入秘密子份额总数:");
        int sharingNums = scanner.nextInt();
        System.out.print("请输入秘密恢复阈值:");
        int threshold = scanner.nextInt();

        return new Classic_CRT_Threshold_Secret_Sharing(parameter, sharingNums, threshold);
    }

    public static void main(String[] args) {

        Classic_CRT_Threshold_Secret_Sharing crtTss = getInstance();

        System.out.println("所需要共享的秘密为：\n" + crtTss.secret);
        // 多个di
        BigInteger[] ds = crtTss.generateNNumbers(crtTss.sharingNums, crtTss.threshold, crtTss.secret);

        // 计算n份子秘密
        for (int i = 0; i < crtTss.sharingNums; i++) {
            crtTss.subSecrets[i] = crtTss.secret.mod(ds[i]);
        }

        for (int i = 0; i < crtTss.subSecrets.length; i++) {
            System.out.println("第" + (i + 1) + "个子秘密(k,d)" + "：(" + crtTss.subSecrets[i].toString()
                    + "," + ds[i].toString() + ")");
        }

        // 用户自行进入恢复
        System.out.print("请输入你拥有的子秘密份额数：");
        int recoverNum = scanner.nextInt();
        BigInteger[] recoverKs = new BigInteger[recoverNum];
        BigInteger[] recoverDs = new BigInteger[recoverNum];
        for (int i = 0; i < recoverNum; i++) {
            System.out.println("———————————————正在进行第" + (i + 1) + "轮输入———————————————");
            System.out.print("请输入k：");
            recoverKs[i] = scanner.nextBigInteger();
            System.out.print("请输入d：");
            recoverDs[i] = scanner.nextBigInteger();
        }

        BigInteger crt = crtTss.crt(recoverKs, recoverDs, recoverNum);
        System.out.println("恢复出来的秘密为：");
        System.out.println(crt);
    }

    private BigInteger[] generateNNumbersBasic(int n) {
        // 生成n个d值并保证它们两两互素
        if (n <= 0) {
            return null;
        }
        BigInteger[] res = new BigInteger[n];
        for (int i = 0; i < n; i++) {
            res[i] = BigInteger.probablePrime(this.parameter / this.threshold + 1, this.RND);
            for (int j = 0; j < i; j++) {
                // 如果不互素，那就重来
                if (!res[i].gcd(res[j]).equals(BigInteger.ONE)) {
                    i--;
                    break;
                }
            }
        }
        // 排序
        Arrays.sort(res);
        return res;
    }

    private BigInteger[] generateNNumbers(int n, int t, BigInteger secret) {
        // 满足要求1
        BigInteger[] res = generateNNumbersBasic(n);
        // 判断是否满足要求2
        BigInteger N = BigInteger.ONE, M = BigInteger.ONE;
        for (int i = 0; i <= t - 1; i++) {
            assert res != null;
            N = N.multiply(res[i]);
        }

        for (int i = n - t + 1; i <= n - 1; i++) {
            assert res != null;
            M = M.multiply(res[i]);
        }
        if (N.compareTo(secret) > 0 && secret.compareTo(M) > 0) {
            return res;
        } else {
            return generateNNumbers(n, t, secret);
        }
    }


    // 中国剩余定理的计算公式
    private BigInteger crt(BigInteger[] a, BigInteger[] p, int num) {
        // 余数数组是a，模数数组是p，方程个数是num
        BigInteger P = BigInteger.ONE;
        for (int i = 0; i < num; i++) {
            P = P.multiply(p[i]);
        }
        BigInteger result = BigInteger.ZERO;
        // 生成逆元数组
        BigInteger[] PInv = new BigInteger[num];
        for (int i = 0; i < num; i++) {
            PInv[i] = P.divide(p[i]).modInverse(p[i]);
            result = result.add(P.divide(p[i]).multiply(PInv[i]).multiply(a[i]));
        }

        return result.mod(P);
    }

}
